//
// Created by ASUS on 2024/11/20/星期三.
//
// Problem: GSS3 - Can you answer these queries III
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP1716
// Memory Limit: 1 MB
// Time Limit: 330000 ms
// DateTime : 2024-11-20 15:45:33
// Author : sunyafei
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct Node{
	int l,r;
	int sum,dat,lmax,rmax;
};

class SegmentTree{
private:
	vector<Node> t;
public:
	SegmentTree(int n){
		t.resize(4*n);
	}

	void pushup(int i){
		t[i].sum=t[2*i].sum+t[2*i+1].sum;
		t[i].lmax=max(t[2*i].lmax,t[2*i].sum+t[2*i+1].lmax);
		t[i].rmax=max(t[2*i].rmax+t[2*i+1].sum,t[2*i+1].rmax);
		t[i].dat=max({t[2*i].dat,t[2*i+1].dat,t[2*i].rmax+t[2*i+1].lmax});
	}

	void build(int i,int l,int r,vector<int>&a){
		t[i].l=l;
		t[i].r=r;
		if(l==r){
			t[i].dat=t[i].sum=t[i].lmax=t[i].rmax=a[l-1];
			return;
		}
		int mid=l+(r-l)/2;
		build(2*i,l,mid,a);
		build(2*i+1,mid+1,r,a);
		pushup(i);
	}

	void update(int i,int l,int r,int x){
		if(t[i].l>r||t[i].r<l) return;
		if(t[i].l>=l&&t[i].r<=r){
			t[i].dat=t[i].sum=t[i].lmax=t[i].rmax=x;
			return;
		}
		update(2*i,l,r,x);
		update(2*i+1,l,r,x);
		pushup(i);
	}
	Node query(int i,int l,int r){
		if(t[i].l>r||t[i].r<l){
			Node fail;
			fail.sum=fail.lmax=fail.rmax=fail.dat=INT_MIN/2;
			return fail;
		};
		if(t[i].l>=l&&t[i].r<=r){
			return t[i];
		}
		Node left=query(2*i,l,r);
		Node right=query(2*i+1,l,r);
		Node res;
		res.sum=left.sum+right.sum;
		res.lmax=max(left.lmax,left.sum+right.lmax);
		res.rmax=max(left.rmax+right.sum,right.rmax);
		res.dat=max({left.dat,right.dat,left.rmax+right.lmax});
		return res;
	}
};

void solve(){
	int n,q;cin>>n>>q;
	vector<int> a(n);
	for(int&x:a)cin>>x;
	SegmentTree t(n+1);
	t.build(1,1,n,a);
	while(q--){
		int op;cin>>op;
		int x,y;cin>>x>>y;
		if(op==2){
			t.update(1,x,x,y);
		}else{
			if(x>y) swap(x,y);
			cout<<t.query(1,x,y).dat<<"\n";
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
		if(t)cout<<"\n";
	}
	return 0;
}
